{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stone Game II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #game-theory #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #博弈 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: stoneGameII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #石子游戏 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>爱丽丝和鲍勃继续他们的石子游戏。许多堆石子&nbsp;<strong>排成一行</strong>，每堆都有正整数颗石子&nbsp;<code>piles[i]</code>。游戏以谁手中的石子最多来决出胜负。</p>\n",
    "\n",
    "<p>爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，<code>M = 1</code>。</p>\n",
    "\n",
    "<p>在每个玩家的回合中，该玩家可以拿走剩下的&nbsp;<strong>前</strong>&nbsp;<code>X</code>&nbsp;堆的所有石子，其中&nbsp;<code>1 &lt;= X &lt;= 2M</code>。然后，令&nbsp;<code>M = max(M, X)</code>。</p>\n",
    "\n",
    "<p>游戏一直持续到所有石子都被拿走。</p>\n",
    "\n",
    "<p>假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [2,7,9,4,4]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [1,2,3,4,5,100]\n",
    "<strong>输出：</strong>104\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= piles.length &lt;= 100</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>1 &lt;= piles[i]&nbsp;&lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stone-game-ii](https://leetcode.cn/problems/stone-game-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stone-game-ii](https://leetcode.cn/problems/stone-game-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,7,9,4,4]', '[1,2,3,4,5,100]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "\n",
    "        s, n = 0, len(piles)\n",
    "\n",
    "        f = [[0] * (n + 1) for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "\n",
    "            s += piles[i]\n",
    "\n",
    "            for m in range(1, i // 2 + 2):\n",
    "\n",
    "                if i + m * 2 >= n:\n",
    "\n",
    "                    f[i][m] = s\n",
    "\n",
    "                else:\n",
    "\n",
    "                    f[i][m] = s - min(f[i + x][max(m, x)] for x in range(1, m * 2 + 1))\n",
    "\n",
    "        return f[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n, memo = len(piles), dict()\n",
    "\n",
    "        # 定义s[i]为第i堆石子到最后一堆石子的总石子数\n",
    "        s = [0] * (n+1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s[i] = s[i + 1] + piles[i]\n",
    "\n",
    "        def dfs(i, M):\n",
    "            \"\"\"定义从第i堆石子开始取，最多取M堆可以得到的最优值\"\"\"\n",
    "\n",
    "            if (i, M) in memo:\n",
    "                return memo[(i, M)]\n",
    "\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            if i + M * 2 >= n:\n",
    "                return s[i]\n",
    "\n",
    "            best = 0\n",
    "            for x in range(1, M * 2 + 1):\n",
    "                best = max(best, s[i] - dfs(i + x, max(x, M)))\n",
    "\n",
    "            memo[(i, M)] = best\n",
    "            return best\n",
    "\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        if n == 1:\n",
    "            return piles[0]\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        total = 0\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            total += piles[i]\n",
    "            for m in range(1,n):\n",
    "                if i + 2 * m >= n:\n",
    "                    dp[i][m] = total\n",
    "                else:\n",
    "                    for x in range(1, 2 * m + 1):\n",
    "                        dp[i][m] = max(dp[i][m], total - dp[i + x][max(m,x)])\n",
    "\n",
    "        return dp[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        s, n = 0, len(piles)\n",
    "        f = [[0] * (n + 1) for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s += piles[i]\n",
    "            for m in range(1, i // 2 + 2):\n",
    "                if i + m * 2 >= n:\n",
    "                    f[i][m] = s\n",
    "                else:\n",
    "                    f[i][m] = s - min(f[i + x][max(m, x)] for x in range(1, m * 2 + 1))\n",
    "        return f[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        s = [0]*len(piles)\n",
    "        s[len(piles)-1] = piles[len(piles)-1]\n",
    "        Dict = {}\n",
    "        for i in range(len(piles) - 2, -1, -1):\n",
    "            s[i] = piles[i] + s[i+1]\n",
    "        def dfs(i: int, M: int) -> int:\n",
    "            if i + 2*M >= len(piles):\n",
    "                return s[i]\n",
    "            if (i,M) in Dict:\n",
    "                return Dict[(i,M)]\n",
    "            else:\n",
    "                Dict[(i,M)] = s[i] - min(dfs(i+x,max(M,x))for x in range(1,2*M + 1))\n",
    "                return Dict[(i,M)] \n",
    "        return dfs(0,1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, ps: List[int]) -> int:\n",
    "        # n = len(s)\n",
    "        # for i in range(n - 2, -1, -1):\n",
    "        #     s[i] += s[i + 1] #后缀和\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i: int, m:int) ->int:\n",
    "        #     if i + m * 2 >= n: #能全拿\n",
    "        #         return s[i]\n",
    "        #     return s[i] - min(dfs(i + x, max(m, x)) for x in range(1, m * 2 + 1))\n",
    "        # return dfs(0, 1)\n",
    "\n",
    "\n",
    "        # 迭代\n",
    "        s, n = 0, len(ps)\n",
    "        f = [[0] * (n +1) for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s += ps[i]\n",
    "            for m in range(1, i // 2 +2):\n",
    "                if i + m * 2 >= n:\n",
    "                    f[i][m] = s\n",
    "                else:\n",
    "                    f[i][m] = s - min(f[i + x][max(m, x)] for x in range(1, m * 2 + 1))\n",
    "\n",
    "        return f[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        s, n = 0, len(piles)\n",
    "        f = [[0] * (n + 1) for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s += piles[i]\n",
    "            for m in range(1, i // 2 + 2):\n",
    "                if i + m * 2 >= n:\n",
    "                    f[i][m] = s\n",
    "                else:\n",
    "                    f[i][m] = s - min(f[i + x][max(m, x)] for x in range(1, m * 2 + 1))\n",
    "        return f[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        s, n = 0, len(piles)\n",
    "        f = [[0] * (n + 1) for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s += piles[i]\n",
    "            for m in range(1, i // 2 + 2):\n",
    "                if i + m * 2 >= n:\n",
    "                    f[i][m] = s\n",
    "                else:\n",
    "                    f[i][m] = s - min(f[i + x][max(m, x)] for x in range(1, m * 2 + 1))\n",
    "\n",
    "        return f[0][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        s, n = 0, len(piles)\n",
    "        f = [[0] * (n + 1) for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s += piles[i]\n",
    "            for m in range(1, i // 2 + 2):\n",
    "                if i + m * 2 >= n:\n",
    "                    f[i][m] = s\n",
    "                else:\n",
    "                    f[i][m] = s - min(f[i + x][max(m, x)] for x in range(1, m * 2 + 1))\n",
    "        return f[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        suffix = [0 for _ in range(n + 1)]\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(51)]\n",
    "        for i in reversed(range(n)):\n",
    "            dp[50][i] = piles[i] + dp[50][i + 1]\n",
    "            \n",
    "        \n",
    "        for i in reversed(range(1, 50)):\n",
    "            for j in reversed(range(n)):\n",
    "                mi = int(1e9)\n",
    "                for k in range(1, min(n - j, 2 * i) + 1):\n",
    "                    k = min(k, 50)\n",
    "                    mi = min(dp[max(i, k)][j + k], mi)\n",
    "                dp[i][j] = dp[50][j] - mi\n",
    "        \n",
    "        # print(dp)\n",
    "\n",
    "        return dp[1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        s,n = 0,len(piles)\n",
    "        f = [[0] * (n + 1) for _ in range(n)]\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            s += piles[i]\n",
    "            for m in range(1, i // 2 + 2):\n",
    "                if i + m * 2 >= n:\n",
    "                    f[i][m] = s\n",
    "                else:\n",
    "                    f[i][m] = s - min(f[i + x][max(m,x)] for x in range(1,2*m+1))        \n",
    "        return f[0][1]\n",
    "        # @cache\n",
    "        # def dfs(i,m) -> int:\n",
    "        #     if i + m * 2 >= n:\n",
    "        #         return piles[i]\n",
    "        #     mn = inf\n",
    "        #     for j in range(1,2 * m + 1):\n",
    "        #         mn = min(mn,dfs(i + j,max(m,j)))\n",
    "        #     return piles[i] - mn\n",
    "        # return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        suffix = [0 for _ in range(n + 1)]\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(51)]\n",
    "        for i in reversed(range(n)):\n",
    "            suffix[i] = piles[i] + suffix[i + 1]\n",
    "            dp[50][i] = suffix[i]\n",
    "        \n",
    "        for i in reversed(range(1, 50)):\n",
    "            for j in reversed(range(n)):\n",
    "                mi = int(1e9)\n",
    "                for k in range(1, min(n - j, 2 * i) + 1):\n",
    "                    k = min(k, 50)\n",
    "                    mi = min(dp[max(i, k)][j + k], mi)\n",
    "                dp[i][j] = suffix[j] - mi\n",
    "        \n",
    "        # print(dp)\n",
    "\n",
    "        return dp[1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n=len(piles)\n",
    "        res=[[0]*(n+1) for _ in range(n+1)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for m in range(1,n+1):\n",
    "                if i+2*m>=n:\n",
    "                    res[i][m]=sum(piles[i:n])\n",
    "                else:\n",
    "                    for choice in range(1,2*m+1):\n",
    "                        res[i][m]=max(res[i][m],sum(piles[i:n])-res[i+choice][max(m,choice)])\n",
    "        return res[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        if len(piles) <= 2: return sum(piles)\n",
    "\n",
    "        n = len(piles)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        tailsum = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            tailsum += piles[i]\n",
    "            for m in range(n-1, 0, -1):\n",
    "                if 2*m >= n-i:\n",
    "                    dp[i][m] = tailsum\n",
    "                else:\n",
    "                    for x in range(1, 2*m+1):\n",
    "                        dp[i][m] = max(dp[i][m], tailsum-dp[i+x][max(m,x)])\n",
    "        return dp[0][1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        # dp[i][m], max alice can win with piles[i:] and m\n",
    "        # dp[i][m] = max(dp[i])\n",
    "        # first calculate the prefix sum\n",
    "        sfx_sum = 0\n",
    "        dp = [[0] * (len(piles) + 1) for _ in range(len(piles))]\n",
    "        for i in range(len(piles) - 1, -1, -1):\n",
    "            sfx_sum += piles[i]\n",
    "            for m in range(1, len(piles) + 1):\n",
    "                for x in range(1, 2 * m + 1):\n",
    "                    if i + x >= len(piles):\n",
    "                        dp[i][m] = max(dp[i][m], sfx_sum)\n",
    "                    else:\n",
    "                        dp[i][m] = max(dp[i][m], sfx_sum - dp[i + x][max(m, x)])\n",
    "        return dp[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        # dp[i][m]: optimal value to collect piles[i:][m] with m\n",
    "        n = len(piles)\n",
    "        dp = [[0] * (n + 1) for _ in range(n)]\n",
    "        suffix_sum = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suffix_sum += piles[i]\n",
    "            for m in range(1, n + 1):\n",
    "                for x in range(1, 2 * m + 1):\n",
    "                    if i + x >= n:\n",
    "                        # player can take all the stones\n",
    "                        dp[i][m] = max(dp[i][m], suffix_sum)\n",
    "                    else:\n",
    "                        dp[i][m] = max(dp[i][m], suffix_sum - dp[i + x][max(x, m)])\n",
    "        return dp[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\r\n",
    "        n = len(piles)\r\n",
    "        prices = [i for i in piles]\r\n",
    "        for i in range(n - 2, -1, -1):\r\n",
    "            prices[i] += prices[i + 1]\r\n",
    "\r\n",
    "        dp = [[0] * (n + 1) for _ in range(n)]\r\n",
    "\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            for j in range(1, n + 1):\r\n",
    "                if i + 2 * j >= n:\r\n",
    "                    dp[i][j] = prices[i]\r\n",
    "                else:\r\n",
    "                    for k in range(1, 2 * j + 1):\r\n",
    "                        dp[i][j] = max(dp[i][j], prices[i] - dp[i + k][max(j, k)])\r\n",
    "        return dp[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "\n",
    "        # dp[i][m]: i:len, m\n",
    "        n_len = len(piles)\n",
    "\n",
    "        if n_len <= 2:\n",
    "            return sum(piles)\n",
    "\n",
    "        dp = [[0 for i in range(n_len)] for j in range(n_len)]\n",
    "        \n",
    "        for i in range(n_len-1, -1, -1):\n",
    "            for m in range(n_len-1, 0, -1):\n",
    "                if n_len-i <= 2 * m:\n",
    "                    dp[i][m] = sum(piles[i:n_len])\n",
    "                else:\n",
    "                    for j in range(i, i + 2 * m):\n",
    "                        new_m = max(m, j-i+1)\n",
    "                        dp[i][m] = max(dp[i][m], sum(piles[i:n_len]) - dp[j+1][new_m])\n",
    "        \n",
    "        # print(dp)\n",
    "        return dp[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        pre_fix = [0]\n",
    "        for x in piles:\n",
    "            pre_fix.append(pre_fix[-1] + x)\n",
    "        \n",
    "        M = 1\n",
    "        f = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n, 0, -1):\n",
    "                t = pre_fix[-1] - pre_fix[i]\n",
    "                if i + 2 * j >= n:\n",
    "                    f[i][j] = t\n",
    "                else:\n",
    "                    for k in range(1, 2 * j + 1):\n",
    "                        f[i][j] = max(f[i][j], t - f[i+k][min(max(j, k), n)])\n",
    "        \n",
    "        return f[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            s[i] += s[i + 1]  # 计算后缀和\n",
    "\n",
    "        # i 表示当前从第几堆开始拿\n",
    "        @cache\n",
    "        def dfs(i: int, M: int) -> int:\n",
    "            if i + M * 2 >= n:  # 能全拿\n",
    "                return s[i]\n",
    "            bob = float('inf')\n",
    "            for x in range(1, M * 2 + 1):\n",
    "                # 如果拿了某几堆石子后，BOB得到的石子数最少，Alice能得到的石子数就是最多的\n",
    "                bob = min(bob, dfs(i + x, max(M, x)))\n",
    "            return s[i] - bob\n",
    "\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            s[i] += s[i + 1]  # 后缀和\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, m: int) -> int:\n",
    "            if i + m * 2 >= n:  # 能全拿\n",
    "                return s[i]\n",
    "            return s[i] - min(dfs(i + x, max(m, x)) for x in range(1, m * 2 + 1))\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, s: List[int]) -> int:\n",
    "        n=len(s)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            s[i]+=s[i+1]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int,m: int)->int:\n",
    "            if i+m*2>=n:\n",
    "                return s[i]\n",
    "            return s[i]-min(dfs(i+x,max(m,x)) for x in range(1,m*2+1))\n",
    "        return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        # f[n][m] 在piles[n:] 中，M为m时，先取的人能够获得的最大石头数量\n",
    "        f = [[0] * (len(piles) + 1) for _ in range(len(piles))]\n",
    "        for n in range(len(piles) - 1, -1, -1):\n",
    "            for m in range(1, len(piles) + 1):\n",
    "                if 2 * m >= len(piles) - n:\n",
    "                    f[n][m] = sum(piles[n:])\n",
    "                else:\n",
    "                    for x in range(1, 2 * m + 1):\n",
    "                        f[n][m] = max(f[n][m], sum(piles[n:]) - f[n + x][max(m, x)])\n",
    "        return f[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        if len(piles) == 1:\n",
    "            return piles[0]\n",
    "        import sys\n",
    "        M = len(piles)\n",
    "        prefix = [0] * (M + 1)\n",
    "        for i in range(M):\n",
    "            prefix[i + 1] = prefix[i] + piles[i]\n",
    "        first = [[0] * M for _ in range(M)]\n",
    "        second = [[0] * M for _ in range(M)]\n",
    "        for i in range(M - 1, -1, -1):\n",
    "            for j in range(M - 1, -1, -1):\n",
    "                if M - i <= 2 * j:\n",
    "                    first[i][j] = prefix[M] - prefix[i]  # sum(piles[i:])\n",
    "                else:\n",
    "                    second[i][j] = sys.maxsize\n",
    "                    for k in range(1, 2 * j + 1):\n",
    "                        # sum(piles[i:i + k]) = prefix[i + k] - prefix[i]\n",
    "                        first[i][j] = max(first[i][j], prefix[i + k] - prefix[i] + second[i + k][max(k, j)])\n",
    "                        second[i][j] = min(second[i][j], first[i + k][max(k, j)])\n",
    "        return first[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            s[i] += s[i + 1]  # 后缀和\n",
    "\n",
    "        # 对于每个节点，由于剩余的石子总数是固定的\n",
    "        # 如果拿了某几堆石子后，对手能得到的石子数最少，那么自己能得到的石子数就是最多的\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, m: int) -> int:\n",
    "            if i + m * 2 >= n:  # 能全拿\n",
    "                return s[i]\n",
    "            return s[i] - min(dfs(i + x, max(m, x)) for x in range(1, m * 2 + 1))\n",
    "        return dfs(0, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 尚未优化，会超时\n",
    "class Solution:\n",
    "    def stoneGameII(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            s[i] += s[i + 1]  # 后缀和\n",
    "\n",
    "        @cache \n",
    "        def dfs(i: int, m: int) -> int:\n",
    "            if i + m * 2 >= n:  # 能全拿\n",
    "                return s[i]\n",
    "            res = inf \n",
    "            for x in range(1, m*2+1):\n",
    "                res = min(res, dfs(i+x, max(m, x)))\n",
    "            return s[i] - res \n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\r\n",
    "        n = len(piles)\r\n",
    "        for i in range(n - 2, -1, -1):\r\n",
    "            piles[i] += piles[i + 1]\r\n",
    "\r\n",
    "        @lru_cache(None)\r\n",
    "        def dfs(i, m):\r\n",
    "            if i + 2 * m >= n: \r\n",
    "                return piles[i]\r\n",
    "            return piles[i] - min(dfs(i + x, max(m, x)) for x in range(1, 2 * m + 1))\r\n",
    "        return dfs(0, 1)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\r\n",
    "        n = len(piles)\r\n",
    "        for i in range(n - 2, -1, -1):\r\n",
    "            piles[i] += piles[i + 1]\r\n",
    "\r\n",
    "        @lru_cache(None)\r\n",
    "        def dfs(i, m):\r\n",
    "            if i + 2 * m >= n: \r\n",
    "                return piles[i]\r\n",
    "            return piles[i] - min(dfs(i + x, max(m, x)) for x in range(1, 2 * m + 1))\r\n",
    "        return dfs(0, 1)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def init(self, piles):\n",
    "        self.n = len(piles)\n",
    "        self.memo = {}\n",
    "        self.psum = self.calPrefixSum(piles)\n",
    "        print(self.psum)\n",
    "\n",
    "    def calPrefixSum(self, piles):\n",
    "        n = len(piles)\n",
    "        psum = [0] * n\n",
    "        psum[0] = piles[0]\n",
    "        for i in range(1, n):\n",
    "            psum[i] = psum[i-1] + piles[i]\n",
    "        return psum\n",
    "\n",
    "    def gameRoundAttacker(self, k, m):\n",
    "        if k >= self.n:\n",
    "            return 0\n",
    "        stamp = '%d:%d:0' % (k,m)\n",
    "        if stamp in self.memo:\n",
    "            return self.memo[stamp]\n",
    "\n",
    "        maxTaken = min(self.n-k, 2*m)\n",
    "        maxStones = 0\n",
    "        for taken in range(1, maxTaken+1):\n",
    "            takenStones = (self.psum[k+taken-1] - self.psum[k-1]) if k > 0 else self.psum[k+taken-1]\n",
    "            scores = takenStones + self.gameRoundDefender(k + taken, max(m, taken))\n",
    "\n",
    "            maxStones = max(maxStones, scores)\n",
    "            #if k == 0:\n",
    "            #    print(\"[debug, attacker, k=0] taken:[%d] taken[%d] final[%d]\" % (taken, takenStones,scores))\n",
    "        \n",
    "        self.memo[stamp] = maxStones\n",
    "        return maxStones\n",
    "\n",
    "    def gameRoundDefender(self, k, m):\n",
    "        if k >= self.n:\n",
    "            return 0\n",
    "        stamp = '%d:%d:1' % (k,m)\n",
    "        if stamp in self.memo:\n",
    "            return self.memo[stamp]\n",
    "        \n",
    "        maxTaken = min(self.n-k, 2*m)\n",
    "        minStones = sys.maxsize\n",
    "        for taken in range(1, maxTaken+1):\n",
    "            lostStones = self.gameRoundAttacker(k+taken, max(m,taken))\n",
    "            minStones = min(minStones, lostStones)\n",
    "        self.memo[stamp] = minStones\n",
    "        return minStones\n",
    "\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        self.init(piles)\n",
    "        points = self.gameRoundAttacker(0, 1)\n",
    "        #print(self.memo)\n",
    "        return points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            piles[i] += piles[i + 1]  # 后缀和\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, m: int) -> int:\n",
    "            if i + m * 2 >= n:  # 能全拿\n",
    "                return piles[i]\n",
    "            return piles[i] - min(dfs(i + x, max(m, x)) for x in range(1, m * 2 + 1))\n",
    "        return dfs(0, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        acc = list(accumulate(piles,initial=0))\n",
    "\n",
    "        @cache\n",
    "        def f(i,m):\n",
    "            if i+m >=n: return acc[-1]-acc[i]\n",
    "            res = float('-inf')\n",
    "            for j in range(i,min(i+2*m,n)):\n",
    "                res = max(res,acc[j+1]-acc[i]-f(j+1,max(m,j+1-i)))\n",
    "            return res\n",
    "        \n",
    "        ans = f(0,1)\n",
    "        return ans+(sum(piles)-ans)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            s[i] += s[i + 1]  # 后缀和\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, m: int) -> int:\n",
    "            if i + m * 2 >= n:  # 能全拿\n",
    "                return s[i]\n",
    "            return s[i] - min(dfs(i + x, max(m, x)) for x in range(1, m * 2 + 1))\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "\n",
    "        # 后缀和计算剩余价值\n",
    "        for i in range(n-2, -1, -1):\n",
    "            piles[i] += piles[i+1]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, m):\n",
    "            if i + 2 * m >= n:\n",
    "                return piles[i]\n",
    "            return piles[i] - min(dfs(i+j, max(m, j)) for j in range(1, 2*m+1))\n",
    "\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        prevsum = list(accumulate(piles))\n",
    "        def sumij(i, j):\n",
    "            if i == 0:\n",
    "                return prevsum[j]\n",
    "            return prevsum[j] - prevsum[i-1]\n",
    "        n = len(piles)\n",
    "        @cache\n",
    "        def f(M, i):\n",
    "            if 2 * M >= n - i:\n",
    "                return sumij(i, n-1)\n",
    "            maxv = 0\n",
    "            for X in range(1, 2 * M + 1):\n",
    "                a = sumij(i, i+X-1)\n",
    "                a += sumij(i+X, n-1) - f(max(M, X), i+X)\n",
    "                if a > maxv:\n",
    "                    maxv = a\n",
    "            return maxv\n",
    "\n",
    "        return f(1, 0)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        # dp[i][j]: 剩余[i:len-1]堆时，M=j的情况下，先取的人能获得的最多石子数量\n",
    "        n = len(piles)\n",
    "        dp = [[0]*(n+1) for _ in range(n)]\n",
    "        # 初始化\n",
    "\n",
    "        # 递推\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for M in range(1,n+1):\n",
    "                if i+2*M>=n: \n",
    "                    dp[i][M] = sum(piles[i:])\n",
    "                else:\n",
    "                    for x in range(1, 2*M+1):\n",
    "                        dp[i][M] = max(dp[i][M], sum(piles[i:])-dp[i+x][max(x,M)])\n",
    "        print(dp)\n",
    "        return dp[0][1]\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# +- 型\n",
    "\n",
    "# 亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。\n",
    "\n",
    "# 亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。\n",
    "\n",
    "# 在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。\n",
    "\n",
    "# 游戏一直持续到所有石子都被拿走。\n",
    "\n",
    "# 假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头\n",
    "\n",
    "# [2,7,9,4,4]\n",
    "# x - y = a\n",
    "# x + y = sum\n",
    "# x = (a + sum) / 2\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(M, i):\n",
    "            if i >= len(piles):\n",
    "                return 0\n",
    "            ans, acc = float(\"-inf\"), 0\n",
    "            for j in range(2 * M):\n",
    "                if i + j < len(piles):\n",
    "                    acc += piles[i + j]\n",
    "                else:\n",
    "                    break\n",
    "                ans = max(ans, acc - dp(max(M, j + 1), i + j + 1))\n",
    "            return ans\n",
    "\n",
    "        return (dp(1, 0) + sum(piles)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        \n",
    "        # 从下标n开始取，可取[1,2*m]堆时，先手能的的最大分\n",
    "        @cache\n",
    "        def dfs(n,m):\n",
    "            if n == len(piles) :\n",
    "                return 0\n",
    "          \n",
    "            total = sum(piles[n:])\n",
    "            score = 0\n",
    "            for x in range(1,2*m+1):\n",
    "                # 取得堆数x超过了剩下的堆数\n",
    "                if x>len(piles)-n:\n",
    "                    break\n",
    "                score = max(score,total-dfs(n+x, max(x,m)) )\n",
    "    \n",
    "            return score\n",
    "        \n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        \n",
    "        prefixSum = [0]\n",
    "        for a in piles:\n",
    "            prefixSum.append(prefixSum[-1] + a)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i, m):\n",
    "            if i == len(piles):\n",
    "                return 0\n",
    "            mx = -inf\n",
    "            for x in range(1, 2 * m + 1):                \n",
    "                if i+x > len(piles):\n",
    "                    break\n",
    "                mx = max(mx, prefixSum[i + x] - prefixSum[i] - dp(i + x, max(m, x)))\n",
    "            return mx\n",
    "            \n",
    "        return (prefixSum[-1]+dp(0, 1)) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        @lru_cache(None)\n",
    "        def stone(n, m):\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            elif n == 1:\n",
    "                return piles[-1]\n",
    "            else:\n",
    "                x = [sum(piles[-n:]) - stone(n - i, max(m, i)) for i in range(1, min(2 * m, n) + 1)]\n",
    "                return max(x)\n",
    "        return stone(n, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, m):\n",
    "            if m * 2 >= n - i:\n",
    "                return s[n] - s[i]\n",
    "            return max(s[n] - s[i] - dfs(i + x, max(m, x)) \n",
    "            for x in range(1, m << 1 | 1))\n",
    "\n",
    "        n = len(piles)\n",
    "        s = list(accumulate(piles, initial=0))\n",
    "        return dfs(0, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "presum = [0] * 101\r\n",
    "class Solution:\r\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\r\n",
    "        n = len(piles)\r\n",
    "        for i in range(n): presum[i + 1] = presum[i] + piles[i]\r\n",
    "\r\n",
    "        @cache\r\n",
    "        def min_max(i: int, M: int) -> int:\r\n",
    "            if i == n: return 0\r\n",
    "            return max(presum[i + x] - presum[i] + (0 if i + x == n else (min(min_max(i + x + y, min(max(M, x, y), (n - i - x - y + 1) >> 1)) for y in range(1, min(max(M, x) << 1, n - i - x) + 1)))) for x in range(1, min(M << 1, n - i) + 1))\r\n",
    "\r\n",
    "        return min_max(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        t=len(piles)\n",
    "        ww={}\n",
    "        for i in range(t-2,-1,-1):\n",
    "            piles[i]+=piles[i+1]\n",
    "        def dfs(x,m):\n",
    "            if (x,m) in ww:\n",
    "                return ww[(x,m)]\n",
    "            ans=0\n",
    "            if t-x<=2*m:\n",
    "                return piles[x]\n",
    "            for i in range(1,1+2*m):\n",
    "                ans=max(ans,piles[x]-dfs(x+i,max(m,i)))\n",
    "            ww[(x,m)]=ans\n",
    "            return ans\n",
    "        return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        add_sum = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            add_sum[i] = add_sum[i-1] + piles[i-1]\n",
    "        self.rec = [[0]*n for _ in range(n)]\n",
    "\n",
    "        def dfs(idx, m):\n",
    "            # idx开始的数组 目前M=m值\n",
    "            # return 先手， 后手分别取得的最大数\n",
    "            total = add_sum[n] - add_sum[idx]\n",
    "            remain = n - idx + 1\n",
    "            if 2*m>=remain:\n",
    "                return total, 0\n",
    "            if not self.rec[idx][m] == 0:\n",
    "                return self.rec[idx][m], total - self.rec[idx][m]\n",
    "            max_res = 0\n",
    "            for i in range(1,2*m+1):\n",
    "                if idx+i>n:\n",
    "                    break\n",
    "                first = add_sum[idx+i] - add_sum[idx]\n",
    "                r1, r2 = dfs(idx+i, max(i,m))\n",
    "                max_res = max(first + r2, max_res)\n",
    "            self.rec[idx][m] = max_res\n",
    "            return max_res, total - max_res\n",
    "        \n",
    "        first, secend = dfs(0, 1)\n",
    "        return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        #官方不好理解\n",
    "        # predixsum=[0]\n",
    "        # for pile in piles:\n",
    "        #     predixsum.append(predixsum[-1]+pile)\n",
    "        # #dfs(i,m) 表示前 i 堆石头已经被取走，当前的M=m的情况下，接下去取石头的玩家可以比另一方多取的石头数\n",
    "        # #取走前i堆，剩下的第i+1堆对应的索引就是i\n",
    "        # def dp(i,m):\n",
    "        #     if i==len(piles):\n",
    "        #         return 0\n",
    "        #     mx=-inf\n",
    "        #     for x in range(1,2*m+1):\n",
    "        #         if i+x>len(piles):\n",
    "        #             break\n",
    "        #         mx=max(mx,predixsum[i+x]-predixsum[i]-dp(i+x,max(x,m)))\n",
    "        #     return mx\n",
    "        # return int((predixsum[-1]+dp(0,1))/2)\n",
    "\n",
    "        #解释版本\n",
    "        n=len(piles)\n",
    "        suffixsum=[0]*(n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suffixsum[i]=piles[i]+suffixsum[i+1]\n",
    "\n",
    "        cache=[[0]*(n+1) for _ in range(n)]\n",
    "        def dfs(i,m):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            if (i+2*m-1)>=(n-1):\n",
    "                return suffixsum[i]\n",
    "            if cache[i][m]==0:\n",
    "                minstones=inf\n",
    "                for x in range(1,2*m+1):\n",
    "                    minstones=min(minstones,dfs(i+x,max(x,m)))\n",
    "                cache[i][m]=suffixsum[i]-minstones\n",
    "            return cache[i][m]\n",
    "        return dfs(0,1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        pq=sum(piles)\n",
    "        m=1\n",
    "        t=len(piles)\n",
    "        ww={}\n",
    "        zz=[]\n",
    "        ff=piles[:]\n",
    "        for i in range(t-2,-1,-1):\n",
    "            ff[i]+=ff[i+1]\n",
    "        def dfs(x,m):\n",
    "            if (x,m) in ww:\n",
    "                return ww[(x,m)]\n",
    "            ans=0\n",
    "            if t-x<=2*m:\n",
    "                return ff[x]\n",
    "            for i in range(1,1+2*m):\n",
    "                ans=max(ans,ff[x]-dfs(x+i,max(m,i)))\n",
    "            ww[(x,m)]=ans\n",
    "            return ans\n",
    "        return (dfs(0,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "presum = [0] * 101\r\n",
    "class Solution:\r\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\r\n",
    "        n = len(piles)\r\n",
    "        for i in range(n): presum[i + 1] = presum[i] + piles[i]\r\n",
    "\r\n",
    "        @cache\r\n",
    "        def min_max(i: int, M: int) -> int:\r\n",
    "            if i == n: return 0\r\n",
    "            return max(presum[i + x] - presum[i] + (0 if i + x == n else (min(min_max(i + x + y, min(max(M, x, y), (n - i - x - y + 1) >> 1)) for y in range(1, min(max(M, x) << 1, n - i - x) + 1)))) for x in range(min(M << 1, n - i), 0, -1))\r\n",
    "\r\n",
    "        return min_max(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        #官方不好理解\n",
    "        # predixsum=[0]\n",
    "        # for pile in piles:\n",
    "        #     predixsum.append(predixsum[-1]+pile)\n",
    "        # #dfs(i,m) 表示前 i 堆石头已经被取走，当前的M=m的情况下，接下去取石头的玩家可以比另一方多取的石头数\n",
    "        # #取走前i堆，剩下的第i+1堆对应的索引就是i\n",
    "        # def dp(i,m):\n",
    "        #     if i==len(piles):\n",
    "        #         return 0\n",
    "        #     mx=-inf\n",
    "        #     for x in range(1,2*m+1):\n",
    "        #         if i+x>len(piles):\n",
    "        #             break\n",
    "        #         mx=max(mx,predixsum[i+x]-predixsum[i]-dp(i+x,max(x,m)))\n",
    "        #     return mx\n",
    "        # return int((predixsum[-1]+dp(0,1))/2)\n",
    "\n",
    "        #解释版本,相对好理解\n",
    "        #dfs(i,m) 表示前 i 堆石头已经被取走（取走前i堆，剩下的第i+1堆对应的索引就是i），当前的M=m的情况下，接下去取石头的玩家获得最大收益\n",
    "        #当前双方已经取走了前i堆石子，还剩下[i, len - 1]堆石子\n",
    "        # 那么我们希望知道在当前的M，我们从这[i, len - 1]堆石子能得到的最大收益，即获取到的最多石子是有多少。\n",
    "        #1.首先明确一个计算公式，我们从位置i取走X堆石子，取走的是[i, i + X - 1]范围的石子，还剩下[i + X , len - 1]堆石子。\n",
    "        #2.如果我们基于当前的M值可以把[i, len - 1]全部取完，那么最大值就是全部取完的值。也就是说i + X - 1 >= len - 1的时候取走了所有的石子。只要最大的X = 2*m满足这个条件即可，即i + 2 * m >= len；\n",
    "        #3.否则我们只能去枚举X ∈ {1， 2*m]的每一种情况，去看我们取走的是[i, i + X - 1]范围的石子之后对手的最大收益是多少。【当前剩余的石子范围变成了[i + X , len - 1]，，M变成max(X, m)，那么对手的最大收益就是dfs(i + X, max(X, m))】，我们要选择是这些情况中对手最大收益最小的那个X，我们的收益 = 当前剩下石子总和sum[i, len - 1] - 对手最小的最大收益min{dfs(i + X, max(X, m))}\n",
    "        #我们可以看到不论是两种情况的哪一种，我们都需要当前剩下石子总和sum[i, len - 1]的值，因为我们使用后缀和的方式先把每个位置i的总和sum[i, len - 1]统计下来。 同时递归的过程，很有可能会对同一个i和m的值dfs(i, m)重复调用，因此我们可以使用一个数组cache[i][m]进行记忆，减少时间开销。\n",
    "        n=len(piles)\n",
    "        suffixsum=[0]*(n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suffixsum[i]=piles[i]+suffixsum[i+1]\n",
    "\n",
    "        cache=[[0]*(2*n) for _ in range(n)]\n",
    "        def dfs(i,m):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            if (i+2*m-1)>=(n-1):\n",
    "                return suffixsum[i]\n",
    "            if cache[i][m]==0:\n",
    "                minstones=inf\n",
    "                for x in range(1,2*m+1):\n",
    "                    minstones=min(minstones,dfs(i+x,max(x,m)))\n",
    "                cache[i][m]=suffixsum[i]-minstones\n",
    "            return cache[i][m]\n",
    "        return dfs(0,1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles) -> int:\n",
    "        n = len(piles)\n",
    "        memo = {}        \n",
    "        # postsum[i] 表示第 i 堆石子到最后一堆石子的总石子数 (剩余石子)\n",
    "        postsum = [0] * (n + 1) # eg [26, 24, 17, 8, 4, 0]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            postsum[i] = postsum[i + 1] + piles[i]\n",
    "            \n",
    "        # dfs(i, M) 表示从第 i 堆石子开始取，最多能取 M 堆石子所能得到的最优值\n",
    "        def dfs(i, M):\n",
    "            if (i, M) in memo:\n",
    "                return memo[(i, M)]\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            # 如果剩余堆数小于等于 2M， 那么可以全拿走 (base case)\n",
    "            if n - i <= M *2:\n",
    "                return postsum[i]\n",
    "            # 枚举拿 x 堆的最优值\n",
    "            res = float('-inf')\n",
    "            # restraint 2: pick from [1, 2M]\n",
    "            for x in range(1, M * 2 + 1):\n",
    "                # 剩余石子减去对方最优策略\n",
    "                res = max(res, postsum[i] - dfs(i + x, max(x, M))) # update new M\n",
    " \n",
    "            memo[(i, M)] = res\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 1) # 1st restraint: init M=1\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "本题难点在于理解两者都发挥“最佳水平”，“最佳水平”在于，每当轮到自己拿石子的时候，要在后继的所有状态中，选择对自己最有利的，那么也就是要遍历后继的所有状态，并选择一个最优解。我们设 dfs(i, M) 表示，当从第 i 堆石子开始拿，允许拿 M <= x <= 2 * M 时，在剩余石子中所能拿到的最大值，那么我们最终要返回的结果就是 dfs(0, 1)。搜索状态时，我们要遵循以下几个原则：\n",
    "\n",
    "如果 i >= n，那么说明石子都已经拿完，直接返回 0；\n",
    "如果 i + M * 2 >= n，那么说明可以把剩余石子一起拿到，就可以直接返回剩余石子的数目 sum(piles[i:])；\n",
    "如果不属于以上两种情况，那么我们需要遍历 1 <= x <= 2 * M，求剩余的最小 dfs(i + x, max(x, M))，也就是自己拿多少的时候，对手拿的石子最少（由于剩余石子数固定，那么最小化对手石子数，就是最大化自己的石子数）。\n",
    "为了防止重复搜索，可以采用记忆化的方法。为了快速求剩余石子数目，可以提前处理后缀和。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles) -> int:\n",
    "        n = len(piles)\n",
    "        memo = {}        \n",
    "   \n",
    "        # dfs(i, M) 表示从第 i 堆石子开始取，最多能取 M 堆石子所能得到的最优值\n",
    "        def dfs(i, M):\n",
    "            if (i, M) in memo:\n",
    "                return memo[(i, M)]\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            # 如果剩余堆数小于等于 2M， 那么可以全拿走\n",
    "            if  n - i <= M *2:\n",
    "                return sum(piles[i: ])\n",
    "            # 枚举拿 x 堆的最优值\n",
    "            res = 0\n",
    "            # restraint 2: pick from [1, 2M]\n",
    "             # explore each x\n",
    "            for x in range(1, M * 2 + 1):\n",
    "                # 剩余石子减去对方最优策略. diff is the current palyers score, keep max\n",
    "                res = max(res, \n",
    "                           sum(piles[i: ]) - dfs(i + x,  max(x, M))) # Then, we set M = max(M, X)\n",
    " \n",
    "            memo[(i, M)] = res\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 1) # 1st restraint: init M=1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "SUPER GOOD ***：https://leetcode-cn.com/problems/stone-game-ii/solution/ji-yi-hua-sou-suo-python3-by-smoon1989/\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        memo = {}\n",
    "\n",
    "        s = [0] * (n + 1)\n",
    "\n",
    "        # 这个倒叙的过程，就是还剩下多少石子\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s[i] = s[i + 1] + piles[i]\n",
    "        \n",
    "        def dfs(i, M):\n",
    "            if (i , M) in memo:\n",
    "                return memo[(i, M)]\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            if i + 2*M >= n:\n",
    "                return s[i] #就是可以返回剩下所有的石子数量\n",
    "            max_ = 0\n",
    "            for j in range(1, 2*M + 1):\n",
    "                max_ = max(max_, s[i] - dfs(i + j, max(j, M)))\n",
    "            memo[(i, M)] = max_\n",
    "            return max_\n",
    "\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        # 数据规模与记忆化\n",
    "        n, memo = len(piles), dict()\n",
    "        \n",
    "        # s[i] 表示第 i 堆石子到最后一堆石子的总石子数\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s[i] = s[i + 1] + piles[i]\n",
    "            \n",
    "        # dfs(i, M) 表示从第 i 堆石子开始取，最多能取 M 堆石子所能得到的最优值\n",
    "        def dfs(i, M):\n",
    "            # 如果已经搜索过，直接返回\n",
    "            if (i, M) in memo:\n",
    "                return memo[(i, M)]\n",
    "            # 溢出拿不到任何石子\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            # 如果剩余堆数小于等于 2M， 那么可以全拿走\n",
    "            if i + M * 2 >= n:\n",
    "                return s[i]\n",
    "            # 枚举拿 x 堆的最优值\n",
    "            best = 0\n",
    "            for x in range(1, M * 2 + 1):\n",
    "                # 剩余石子减去对方最优策略\n",
    "                best = max(best, s[i] - dfs(i + x, max(x, M)))\n",
    "            # 记忆化\n",
    "            memo[(i, M)] = best\n",
    "            return best\n",
    "        \n",
    "        return dfs(0, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        # 数据规模与记忆化\n",
    "        n, memo = len(piles), dict()\n",
    "        \n",
    "        # s[i] 表示第 i 堆石子到最后一堆石子的总石子数\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s[i] = s[i + 1] + piles[i]\n",
    "            \n",
    "        # dfs(i, M) 表示从第 i 堆石子开始取，最多能取 M 堆石子所能得到的最优值\n",
    "        def dfs(i, M):\n",
    "            # 如果已经搜索过，直接返回\n",
    "            if (i, M) in memo:\n",
    "                return memo[(i, M)]\n",
    "            # 溢出拿不到任何石子\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            # 如果剩余堆数小于等于 2M， 那么可以全拿走\n",
    "            if i + M * 2 >= n:\n",
    "                return s[i]\n",
    "            # 枚举拿 x 堆的最优值\n",
    "            best = 0\n",
    "            for x in range(1, M * 2 + 1):\n",
    "                # 剩余石子减去对方最优策略\n",
    "                best = max(best, s[i] - dfs(i + x, max(x, M)))\n",
    "            # 记忆化\n",
    "            memo[(i, M)] = best\n",
    "            return best\n",
    "        \n",
    "        return dfs(0, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        sum = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i == n - 1:\n",
    "                sum[i] = piles[i]\n",
    "            else:\n",
    "                sum[i] = sum[i + 1] + piles[i]\n",
    "        dp = [[0] * (2 * n) for _ in range(n)]\n",
    "        \n",
    "        def dfs(index, M):\n",
    "            if index == n:\n",
    "                return 0\n",
    "            if n - index <= 2 * M:\n",
    "                return sum[index]\n",
    "            if dp[index][M] != 0:\n",
    "                return dp[index][M]\n",
    "            my_min = float(\"inf\")\n",
    "            for i in range(1, 2 * M + 1):\n",
    "                my_min = min(my_min, dfs(index + i, max(M, i)))\n",
    "            dp[index][M] = sum[index] - my_min\n",
    "            return dp[index][M]\n",
    "\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        #官方不好理解\n",
    "        # predixsum=[0]\n",
    "        # for pile in piles:\n",
    "        #     predixsum.append(predixsum[-1]+pile)\n",
    "        # #dfs(i,m) 表示前 i 堆石头已经被取走，当前的M=m的情况下，接下去取石头的玩家可以比另一方多取的石头数\n",
    "        # #取走前i堆，剩下的第i+1堆对应的索引就是i\n",
    "        # def dp(i,m):\n",
    "        #     if i==len(piles):\n",
    "        #         return 0\n",
    "        #     mx=-inf\n",
    "        #     for x in range(1,2*m+1):\n",
    "        #         if i+x>len(piles):\n",
    "        #             break\n",
    "        #         mx=max(mx,predixsum[i+x]-predixsum[i]-dp(i+x,max(x,m)))\n",
    "        #     return mx\n",
    "        # return int((predixsum[-1]+dp(0,1))/2)\n",
    "\n",
    "        #解释版本,相对好理解\n",
    "        #dfs(i,m) 表示前 i 堆石头已经被取走（取走前i堆，剩下的第i+1堆对应的索引就是i），当前的M=m的情况下，接下去取石头的玩家获得最大收益\n",
    "        #当前双方已经取走了前i堆石子，还剩下[i, len - 1]堆石子\n",
    "        # 那么我们希望知道在当前的M，我们从这[i, len - 1]堆石子能得到的最大收益，即获取到的最多石子是有多少。\n",
    "        #1.首先明确一个计算公式，我们从位置i取走X堆石子，取走的是[i, i + X - 1]范围的石子，还剩下[i + X , len - 1]堆石子。\n",
    "        #2.如果我们基于当前的M值可以把[i, len - 1]全部取完，那么最大值就是全部取完的值。也就是说i + X - 1 >= len - 1的时候取走了所有的石子。只要最大的X = 2*m满足这个条件即可，即i + 2 * m >= len；\n",
    "        #3.否则我们只能去枚举X ∈ {1， 2*m]的每一种情况，去看我们取走的是[i, i + X - 1]范围的石子之后对手的最大收益是多少。【当前剩余的石子范围变成了[i + X , len - 1]，，M变成max(X, m)，那么对手的最大收益就是dfs(i + X, max(X, m))】，我们要选择是这些情况中对手最大收益最小的那个X，我们的收益 = 当前剩下石子总和sum[i, len - 1] - 对手最小的最大收益min{dfs(i + X, max(X, m))}\n",
    "        #我们可以看到不论是两种情况的哪一种，我们都需要当前剩下石子总和sum[i, len - 1]的值，因为我们使用后缀和的方式先把每个位置i的总和sum[i, len - 1]统计下来。 同时递归的过程，很有可能会对同一个i和m的值dfs(i, m)重复调用，因此我们可以使用一个数组cache[i][m]进行记忆，减少时间开销。\n",
    "        n=len(piles)\n",
    "        suffixsum=[0]*(n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suffixsum[i]=piles[i]+suffixsum[i+1]\n",
    "\n",
    "        cache=[[0]*(2*n) for _ in range(n)]\n",
    "        def dfs(i,m):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            if (i+2*m-1)>=(n-1):\n",
    "                return suffixsum[i]\n",
    "            if cache[i][m]==0:\n",
    "                minstones=inf\n",
    "                for x in range(1,2*m+1):\n",
    "                    minstones=min(minstones,dfs(i+x,max(x,m)))\n",
    "                cache[i][m]=suffixsum[i]-minstones\n",
    "            return cache[i][m]\n",
    "        return dfs(0,1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, m):\n",
    "            s = sum(piles[i:])\n",
    "            if 2 * m >= -i:\n",
    "                return s\n",
    "            else:\n",
    "                return s - min([dfs(i + x, m)  for x in range(1, m)] + [dfs(i + x, x) for x in range(m, m * 2 + 1)])\n",
    "                \n",
    "        return dfs(-len(piles), 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        ss = list(accumulate(piles, initial=0))\n",
    "        inf = float('inf')\n",
    "        # print(ss)\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, M):\n",
    "            if idx >= n: return 0\n",
    "            if n - idx <= M: return ss[n] - ss[idx]\n",
    "            res = inf\n",
    "            for i in range(1, 2*M+1):\n",
    "                res = min(res, dfs(idx+i, max(M, i)))\n",
    "            res = ss[n] - ss[idx] - res\n",
    "            return res\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        presum = [0] * (n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            presum[i] = presum[i+1] + piles[i]\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, m):\n",
    "            if i + 2 * m >= n:\n",
    "                return presum[i]\n",
    "            return presum[i] - min(dfs(i+x, max(m, x)) for x in range(1, 2*m+1))\n",
    "        return dfs(0, 1) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        s = [0]*(n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            s[i] += s[i+1] + piles[i] # 后缀和\n",
    "\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, m):\n",
    "            if i+2*m > n:\n",
    "                return s[i]\n",
    "            \n",
    "            res = inf\n",
    "            for j in range(i, i+2*m):\n",
    "                x = j-i+1\n",
    "                res = min(res, dfs(j+1, max(m,x)))\n",
    "            \n",
    "            return s[i] - res \n",
    "        \n",
    "        return dfs(0, 1)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        ss = list(accumulate(piles, initial=0))\n",
    "        inf = float('inf')\n",
    "        # print(ss)\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, M):\n",
    "            if idx >= n: return 0\n",
    "            if n - idx <= M: return ss[n] - ss[idx]\n",
    "            res = inf\n",
    "            for i in range(1, 2*M+1):\n",
    "                res = min(res, dfs(idx+i, max(M, i)))\n",
    "            res = ss[n] - ss[idx] - res\n",
    "            return res\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        t=len(piles)\n",
    "        ww={}\n",
    "        for i in range(t-2,-1,-1):\n",
    "            piles[i]+=piles[i+1]\n",
    "        @cache\n",
    "        def dfs(x,m):\n",
    "            if t-x<=2*m:\n",
    "                return piles[x]\n",
    "            return piles[x]-min(dfs(i + x, max(m, i)) for i in range(1, m * 2 + 1))\n",
    "        return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            piles[i] += piles[i + 1]\n",
    "        @cache\n",
    "        def dfs(i: int, m: int) -> int:\n",
    "            if i + m * 2 >= n:\n",
    "                return piles[i]\n",
    "            return piles[i] - min(dfs(i + x, max(m, x)) for x in range(1, m * 2 + 1))\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            s[i] += s[i + 1]  # 后缀和\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, m: int) -> int:\n",
    "            if i + m * 2 >= n:  # 能全拿\n",
    "                return s[i]\n",
    "            return s[i] - min(dfs(i + x, max(m, x)) for x in range(1, m * 2 + 1))\n",
    "        return dfs(0, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            piles[i] += piles[i + 1]\n",
    "        @cache\n",
    "        def dfs(i,m) -> int:\n",
    "            if i + m * 2 >= n:\n",
    "                return piles[i]\n",
    "            mn = inf\n",
    "            for j in range(1,2 * m + 1):\n",
    "                mn = min(mn,dfs(i + j,max(m,j)))\n",
    "            return piles[i] - mn\n",
    "        return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        sufsum = [0] * n\n",
    "        sufsum[-1] = piles[-1]\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            sufsum[i] = sufsum[i + 1] + piles[i]\n",
    "        @cache\n",
    "        def dfs(i,m) -> int:\n",
    "            if i + m * 2 >= n:\n",
    "                return sufsum[i]\n",
    "            mn = inf\n",
    "            for j in range(1,2 * m + 1):\n",
    "                mn = min(mn,dfs(i + j,max(m,j)))\n",
    "            return sufsum[i] - mn\n",
    "        return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            piles[i] += piles[i + 1]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(left, M):\n",
    "            if left + M * 2 >= n:\n",
    "                return piles[left]\n",
    "            return piles[left] - min(dfs(left + x, max(x, M)) for x in range(1, 2 * M + 1))\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "\n",
    "        pre = [0]\n",
    "        for a in piles:\n",
    "            pre.append(pre[-1]+a)\n",
    "\n",
    "        n = len(piles)\n",
    "        @lru_cache(cache)\n",
    "        def dp(i, m):\n",
    "            if i==n:\n",
    "                return 0\n",
    "            mx = -inf \n",
    "            for k in range(1, 2*m+1):\n",
    "                if i+k > n:\n",
    "                    break\n",
    "                mx = max(mx, pre[i+k]-pre[i]-dp(i+k, max(m,k)))\n",
    "            return mx \n",
    "        return (dp(0, 1) + pre[-1]) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(u, M):\n",
    "            if u > n: return 0\n",
    "            ans = -inf\n",
    "            s = 0\n",
    "            for i in range(u, min(n + 1, u + 2 * M)):\n",
    "                s += piles[i - 1]\n",
    "                ans = max(ans, s - dfs(i + 1, max(i - u + 1, M)))\n",
    "            return ans\n",
    "        \n",
    "        n = len(piles)\n",
    "        return dfs(1, 1) + sum(piles) >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, s: List[int]) -> int:\n",
    "        n=len(s)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            s[i] += s[i+1]\n",
    "        @cache\n",
    "        def dfs(i,m):\n",
    "            if i+2*m>=n:\n",
    "                return s[i]\n",
    "            return s[i]-min(dfs(i+x,max(m,x)) for x in range(1,m*2+1))\n",
    "        return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n=len(piles)\n",
    "        #对抗思想、GNN网络\n",
    "        #求后缀和\n",
    "        s=[0]*n\n",
    "        s[-1]=piles[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            s[i]=s[i+1]+piles[i]\n",
    "        #只考虑了A并没有考虑B，需要A和B都是以最优方式拿石子\n",
    "        @cache\n",
    "        def dfs(i,x):\n",
    "            if n-i<=2*x:\n",
    "                return s[i]\n",
    "            return s[i]-min(dfs(i+k,max(k,x)) for k in range(1,2*x+1))\n",
    "        return dfs(0,1)   \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n=len(piles)\n",
    "        m=1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            piles[i]+=piles[i+1]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i:int, m:int)-> int:\n",
    "            if i+m*2>=n:\n",
    "                return piles[i]\n",
    "            \n",
    "            return piles[i]-min(dfs(i+x,max(m,x)) for x in range(1,m*2+1))\n",
    "        return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, m):\n",
    "            if m * 2 >= n - i:\n",
    "                return s[n] - s[i]\n",
    "            return max(s[n] - s[i] - dfs(i + x, max(m, x)) for x in range(1, m << 1 | 1))\n",
    "\n",
    "        n = len(piles)\n",
    "        s = list(accumulate(piles, initial=0))\n",
    "        return dfs(0, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        \n",
    "        prefixSum = [0]\n",
    "        for a in piles:\n",
    "            prefixSum.append(prefixSum[-1] + a)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i, m):\n",
    "            if i == len(piles):\n",
    "                return 0\n",
    "            mx = -inf\n",
    "            for x in range(1, 2 * m + 1):                \n",
    "                if i+x > len(piles):\n",
    "                    break\n",
    "                mx = max(mx, prefixSum[i + x] - prefixSum[i] - dp(i + x, max(m, x)))\n",
    "            return mx\n",
    "            \n",
    "        return (prefixSum[-1]+dp(0, 1)) // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        s = list(accumulate(piles, initial=0))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, m):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            ans = -inf\n",
    "            for x in range(1, 2 * m + 1):\n",
    "                if i + x > n:\n",
    "                    break\n",
    "                ans = max(ans, s[i + x] - s[i] - dfs(i + x, max(m, x)))\n",
    "            return ans\n",
    "\n",
    "        return (sum(piles) + dfs(0, 1)) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: [int]) -> int:\n",
    "        total=sum(piles)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(ll: int, rr: int, M:int):\n",
    "            if ll+2*M-1>=rr:\n",
    "                return sum(piles[ll::])\n",
    "\n",
    "            maxed=-sys.maxsize\n",
    "            cur=0\n",
    "            tot=0\n",
    "            while ll+cur<=rr and cur+1<=2*M:\n",
    "                tot+=piles[ll+cur]\n",
    "                maxed=max(maxed,tot-dfs(ll+cur+1,rr,max(cur+1,M)))\n",
    "                cur+=1\n",
    "            print(ll,rr,M,maxed)\n",
    "            return maxed\n",
    "\n",
    "        ali=dfs(0,len(piles)-1,1)\n",
    "#        print(ali,total)\n",
    "        return (ali+total)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        prefixSum = [0]\n",
    "        for a in piles:\n",
    "            prefixSum.append(prefixSum[-1] + a)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i, m):\n",
    "            if i == len(piles):\n",
    "                return 0\n",
    "            mx = -inf \n",
    "            for x in range(1, 2 * m + 1):\n",
    "                if i + x > len(piles):\n",
    "                    break \n",
    "                mx = max(mx, prefixSum[i + x] - prefixSum[i] - dp(i + x, max(m, x)))\n",
    "            return mx \n",
    "        \n",
    "        return (prefixSum[-1] + dp(0, 1)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        for pile in piles:\n",
    "            pre.append(pre[-1]+pile)\n",
    "        n = len(piles)\n",
    "        @lru_cache(None)\n",
    "        def dp(i, m):\n",
    "            #从index=i开始取\n",
    "            if i == n:\n",
    "                return 0\n",
    "            mx = -inf\n",
    "            for k in range(1, 2*m+1):\n",
    "                 #i+k为下一次开始取的index\n",
    "                if i+k > n:\n",
    "                    break\n",
    "                mx = max(mx, pre[i+k] - pre[i] - dp(i+k, max(m, k)))\n",
    "            return mx\n",
    "\n",
    "        return (dp(0, 1)+pre[-1])//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        from functools import lru_cache\n",
    "        # prefix_sum = [0]\n",
    "        # for a in piles:\n",
    "        #     prefix_sum.append(prefix_sum[-1] + a)\n",
    "        \n",
    "        # @lru_cache(None)\n",
    "        # def dp(i, m):\n",
    "        #     if i == len(piles):\n",
    "        #         return 0\n",
    "        #     mx = -10**5\n",
    "        #     for x in range(1, 2 * m + 1):\n",
    "        #         if i + x > len(piles):\n",
    "        #             break\n",
    "        #         mx = max(mx, prefix_sum[i+x] - prefix_sum[i] - dp(i + x, max(m, x)))\n",
    "        #     return mx\n",
    "        # return (prefix_sum[-1]+dp(0, 1)) // 2\n",
    "        \n",
    "        prefix_sum = [0]\n",
    "        for n in piles:\n",
    "            prefix_sum.append(prefix_sum[-1] + n)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i, m):\n",
    "            if i == len(piles):\n",
    "                return 0\n",
    "            mx = -10**5\n",
    "            for x in range(1, 2*m + 1):\n",
    "                if i + x > len(piles):\n",
    "                    break\n",
    "                mx = max(mx, prefix_sum[i + x] - prefix_sum[i] - dp(i+x, max(m, x)))\n",
    "            return mx\n",
    "        return (prefix_sum[-1] + dp(0, 1)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        for a in piles:\n",
    "            pre.append(pre[-1]+a)\n",
    "        \n",
    "        n = len(piles)\n",
    "\n",
    "        @lru_cache(cache)\n",
    "        def dp(i, m):\n",
    "            if i==n:\n",
    "                return 0\n",
    "            mx = -inf \n",
    "            for k in range(1, 2*m+1):\n",
    "                if i+k > n:\n",
    "                    break\n",
    "                mx = max(mx, pre[i+k]-pre[i]-dp(i+k, max(m,k)))\n",
    "            return mx \n",
    "        return (dp(0, 1) + pre[-1]) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#记忆化搜索 or 动态规划\n",
    "#时间复杂度O(n^3)，其中O(n^2)为状态数，O(n)为计算每个状态结果所用的时间\n",
    "#空间复杂度O(n^2)\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def stoneGameII(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        if n<=2:\n",
    "            return sum(s)\n",
    "        prefix = [0]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            prefix[i] = prefix[i-1]+s[i-1]\n",
    "        @cache\n",
    "        def dfs(i, m):\n",
    "            if 2*m>=(n-i):\n",
    "                return prefix[-1]-prefix[i]\n",
    "            res = prefix[-1]-prefix[i]-min(dfs(j, max(m, j-i)) for j in range(i+1, i+2*m+1))\n",
    "            return res\n",
    "        return dfs(0, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameII(self, piles: List[int]) -> int:\n",
    "        \n",
    "        prefixSum = [0]\n",
    "        for a in piles:\n",
    "            prefixSum.append(prefixSum[-1] + a)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i, m):\n",
    "            if i == len(piles):\n",
    "                return 0\n",
    "            mx = -inf\n",
    "            for x in range(1, 2 * m + 1):                \n",
    "                if i+x > len(piles):\n",
    "                    break\n",
    "                mx = max(mx, prefixSum[i + x] - prefixSum[i] - dp(i + x, max(m, x)))\n",
    "            return mx\n",
    "            \n",
    "        return (prefixSum[-1]+dp(0, 1)) // 2\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
